from collections import deque
import Vertex

# implementing Graph
# assumptions:    1. the Graph is always connected
#                 2. the vertex is an external class 
class Graph:
    def __init__(self):
        self.Root = Vertex.Vertex(0)
        self.Count = 0
        self.Vertices = set()
    
    # implements addition of edge/vertex to the Graph
    # in case of edition of vertex, the input would be the id
    # of the vertex that would be the direct father of the new one
    def addVertex(self,fatherID,childID = None):
        if fatherID == -1:
            self.Count = self.Count + 1
            newChild = self.Root.addChild(self.Count)
            self.Vertices.add(newChild)
            return True
        father = self.findVertex(fatherID)
        if childID != None:
            child = self.findVertex(childID)
            if child != None:
                father.addExistingChild(child)
                return True
            else:
                return False
        if father != None:
            self.Count = self.Count + 1
            newChild = father.addChild(self.Count) 
            self.Vertices.add(newChild)
            return True
        return False
    
    # clears the Visited flag on every vertex
    def ClearVisited(self):
        for vertex in self.Vertices:
            vertex.Visited = False   
             
    # gets an id for a vertex to find
    # returns the vertex if exists and None if not
    # the method uses the hash structure of python
    def findVertex(self,ID):
        for vertex in self.Vertices:
            if vertex.Id == ID:
                return vertex
        return None
    
    # call for DFS search implemented in vertex
    def DFSearch(self,ID):
        tmpFind = self.Root.DFSfind(ID)
        if tmpFind == None:
            print("DFS did not Find")
        else:
            print("DFS find " + str(ID))
        self.ClearVisited() 
        
    # implementation of BFS search
    def BFSearch(self,ID):
        fifo = deque()  
        fifo.append(self.Root)
        while len(fifo) > 0:
            for i in range(len(fifo)):
                tmpVertex = fifo.pop()
                print("BFS visiting " + str(tmpVertex.Id))
                if tmpVertex.Id == ID:
                    print("Find " + str(ID))
                    return tmpVertex
                for vertex in tmpVertex.Children:
                    if vertex.Visited == False:
                        fifo.append(vertex)
                        vertex.Visited = True
        if len(fifo) == 0:
            print("BFS did Not find")
        else:
            print("BFS find " + str(ID))
        self.ClearVisited()
    
    # calling iterative deepening dfs search
    def IDDFS(self,ID,maxDepth):
        for i in range(maxDepth):
            tmpFind = self.Root.DFSfind(ID,i)
            self.ClearVisited()
            if tmpFind != None:
                break                
        if tmpFind == None:
            print("IDDFS did Not Find")
        else:
            print("IDDFS Find " + str(ID))
            
    # printing all edges of the graph            
    def printGraph(self):
        print("count = " + str(self.Count))
        for vertex in self.Vertices:
            for child in vertex.Children:
                print(str(vertex.Id) + " -> " + str(child.Id)) 
        print("FIN")   